import java.util.Arrays;
import java.util.Scanner;

public class arrayPra {

    //1.递归求阶乘

    public static int factorial(int n){
        if(n==1){
            return 1;
        }
        return n*factorial(n-1);
    }

    public static void main1(String[] args) {
        Scanner scan=new Scanner(System.in);
        System.out.println("输入一个整数：");
        int n=scan.nextInt();
        System.out.println(factorial(n));

    }

    //2.求和
    public static int add(int n){
        if(n==1){
            return 1;
        }
        return n+add(n-1);
    }

    public static void main2(String[] args) {
        System.out.println(add(10));
    }

    //3.打印

    public static void pri(int n){
        if(n<10){
            System.out.print(n+" ");
        }
        else {
            pri(n / 10);
            int x = n % 10;
            System.out.print(x + " ");
        }
    }
    public static void main3(String[] args) {
         pri(1234);
    }


    //4.返回各位之和

    public static int everyAdd(int n){
        if(n<10){
            System.out.print(n);
            return n;
        }
        else{
           int ret=everyAdd(n/10);
            int x=n%10;
            System.out.print("+"+x);

            return x+ret;
        }
    }
    public static void main4(String[] args) {
        System.out.println("="+everyAdd(1238));
    }



    //5.斐波那契

    public static int fib(int n){
        if(n==1||n==2){
            return 1;
        }
        return fib(n-1)+fib(n-2);

    }
    public static void main5(String[] args) {
        System.out.println(fib(14));
    }


    //6.汉诺塔
    public static void hanoi(int n,char A,char B,char C){
            if(n==1){
                System.out.println(A+"->"+C);
            }
            else{
            hanoi(n-1,A,C,B);
            System.out.println(A+"->"+C);
            hanoi(n-1,B,A,C);
            }
    }
    public static void main6(String[] args) {
        hanoi(3,'X','Y','Z');
    }


    //7.原数组为 {1, 2, 3}, 修改之后为 {2, 4, 6}
    public static void tranform(int[] arr2){
        for(int i=0;i<arr2.length;i++){
            arr2[i]=arr2[i]*2;
        }
    }
    public static void main7(String[] args) {
        int[] arr1={1,2,3};
        System.out.println("修改前；");
        System.out.println(Arrays.toString(arr1));
        tranform(arr1);
        System.out.println("修改后；");
        System.out.println(Arrays.toString(arr1));


    }


    //8.调整数组顺序使得奇数位于偶数之前。调整之后，不关心大小顺序。
    //
    //如数组：[1,2,3,4,5,6]
    //
    //调整后可能是：[1, 5, 3, 4, 2, 6]

    public  static void oddEvenSort(int[] arr2){
        int[] newarr=new int[arr2.length];
        int k=0;
        for(int i=0;i<arr2.length;i++){
            if(arr2[i]%2!=0){
                newarr[k]=arr2[i];
                k++;
            }
        }
        for(int i=0;i<arr2.length;i++){
            if(arr2[i]%2==0){
                newarr[k]=arr2[i];
                k++;
            }
        }
        System.out.println(Arrays.toString(newarr));
    }
    public static void main8(String[] args) {
        int[] arr1={1,2,3,4,5,6};
        oddEvenSort(arr1);
    }


    //9.二分查找
    public static void binary(int[] arr2,int x){
        int left=0;
        int right=arr2.length-1;
        int mid=(left+right)/2;
        while(left<=right)
        if(arr2[mid]>x){
            right=mid-1;
            mid=(left+right)/2;
        }
        else if(arr2[mid]<x){
           left=mid+1;
            mid=(left+right)/2;
        }
        else{
            System.out.println("找到了,下标为："+mid);
            break;
        }
    }
    public static void main9(String[] args) {
        int[] arr={1,2,3,4,5,6,7,8,9,10};
        binary(arr,9);
    }


    //10.两数之和
    //输入：nums = [2,7,11,15], target = 9
    //
    //输出：[0,1]
    //
    //解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
    //要求：数组中同一个元素在答案里不能重复出现。

    public static void add(int[] arr2,int x){
        for(int i=0;i<arr2.length;i++){
            for(int j=0;j< arr2.length;j++){
                if(arr2[i]+arr2[j]==x){
                    if(i==j){
                        continue;
                    }
                    System.out.println("["+i+","+j+"]");
                }
            }
        }
    }
    public static void main10(String[] args) {
        int[] arr={1,2,3,4,5,6,7,8,11};
        add(arr,12);
    }


    //11.输入: [2,2,1]
    //输出: 1
    //示例 2:
    //
    //输入: [4,1,2,1,2]
    //输出: 4

    public static void only(int[] arr2) {

        for (int i = 0; i < arr2.length; i++) {
            int count = 0;
            for (int j = 0; j < arr2.length; j++) {
                if (arr2[i] == arr2[j]) {
                    count++;
                }
            }
            if (count == 1) {
                System.out.println(arr2[i]);
            }
        }
    }

    public static void main11(String[] args) {
        int[] arr={9,9,3,3,2,2,4,4,67,5,5};
        only(arr);
    }



    //12.示例 1：
    //
    //输入：[3,2,3]
    //输出：3
    //示例 2：
    //
    //输入：[2,2,1,1,1,2,2]
    //输出：2
    //给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

    public static void majorityElement(int[] arr2) {
        int n = arr2.length/2;
        Arrays.sort(arr2);
        for (int i = 0; i < arr2.length; i++) {
            if(i>=1&&arr2[i]==arr2[i-1]){
                continue;
            }
            int count = 0;
            for (int j = 0; j < arr2.length; j++) {

                if(arr2[i]==arr2[j]){
                    count++;

                }
            }

            if(count>n){

                System.out.println(arr2[i]+" ");
            }
        }
    }
    public static void main12(String[] args) {
        int[] arr={2,2,2,1,1,1,2,2,3};
        majorityElement(arr);
    }


    //13.给你一个整数数组 arr，请你判断数组中是否存在连续三个元素都是奇数的情况：如果存在，请返回 true ；否则，返回 false 。
    //
    //
    //
    //示例 1：
    //
    //
    //
    //输入：arr = [2,6,4,1]
    //
    //输出：false
    //
    //解释：不存在连续三个元素都是奇数的情况。
    //
    //示例 2：
    //
    //
    //
    //输入：arr = [1,2,34,3,4,5,7,23,12]
    //
    //输出：true
    //
    //解释：存在连续三个元素都是奇数的情况，即 [5,7,23]

    public static boolean threeOdd(int[] arr){
        for(int i=1;i<arr.length-1;i++){
            if((arr[i-1]%2!=0)&&(arr[i]%2!=0)&&(arr[i+1]%2!=0)){

                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] arr={1,2,34,3,4,5,23,12,13,16,17};
        System.out.println(threeOdd(arr));
    }
}






